Tavole di verità dei connettivi

Il significato dei vari connettivi logici \(\neg,\wedge,\vee,\to,\leftrightarrow\) introdotti nella sezione precedente è completamente descritto dalle loro tavole di verità.

La tavola di verità di un connettivo è una tabella che lo caratterizza completamente descrivendo in quali casi l’espressione ottenuta “applicando” il connettivo risulta vera.

Negazione

Consideriamo il connettivo \(\neg\). Il suo significato può essere descritto con precisione dicendo che se \(\mathrm{P}\) è vera allora \(\neg \mathrm{P}\) è falsa, mentre se \(\mathrm{P}\) è falsa allora \(\neg \mathrm{P}\) è vera.

Questa informazione può essere rappresentata graficamente nella seguente tabella, che è la

Tavola di verità di \(\neg\)

I simboli V e F denotano, rispettivamente, il vero e il falso. Ogni riga della tavola di verità (in questo caso, due righe) descrive una possibile situazione:

• la prima riga dice che se \(\mathrm{P}\) è vera, allora \(\neg \mathrm{P}\) è falsa;

• la seconda riga dice che se invece \(\mathrm{P}\) è falsa, allora \(\neg \mathrm{P}\) è vera.

Tavola di verità di \(\neg\)

Poiché l’affermazione \(\mathrm{P}\), qualunque essa sia e in qualunque contesto la valutiamo, dovrà essere vera o falsa, la tabella precedente descrive in maniera completa ed esaustiva il significato di \(\neg\) fornendo una regola chiara e non ambigua per “calcolare” se in un dato contesto l’espressione \(\neg \mathrm{P}\) sia vera o falsa a seconda della verità o meno di \(\mathrm{P}\).

Congiunzione

Nel caso della congiunzione \(\wedge\), abbiamo che \(\mathrm{P} \wedge \mathrm{Q}\) è vera se e solo se \(\mathrm{P}\) e \(\mathrm{Q}\) sono entrambe vere. Questo può essere riassunto graficamente nella

Tavola di verità di \(\wedge\)

In questo caso abbiamo infatti quattro possibilità: \(\mathrm{P}\) e \(\mathrm{Q}\) entrambe vere, \(\mathrm{P}\) vera e \(\mathrm{Q}\) falsa, \(\mathrm{P}\) falsa e \(\mathrm{Q}\) vera, oppure \(\mathrm{P}\) e \(\mathrm{Q}\) entrambe false. Per ciascuna scelta di \(\mathrm{P}\) e \(\mathrm{Q}\) e in qualunque contesto ci troviamo, ricadremo certamente in una di queste quattro possibilità e controllando la riga corrispondente nella tabella precedente potremo “calcolare” se \(\mathrm{P} \wedge \mathrm{Q}\) sia vera o no in tale circostanza.

Ad esempio, se \(\mathrm{P}\) è falsa e \(\mathrm{Q}\) è vera allora \(\mathrm{P} \wedge \mathrm{Q}\) sarà falsa, mentre se \(\mathrm{P}\) e \(\mathrm{Q}\) sono entrambe vere allora \(\mathrm{P} \wedge \mathrm{Q}\) sarà vera.

Disgiunzione

Similmente, anche le tavole di verità dei rimanenti connettivi ne descrivono completamente il significato.

L’affermazione \(\mathrm{P} \vee \mathrm{Q}\) è vera se e solo se almeno una tra \(\mathrm{P}\) e \(\mathrm{Q}\) è vera.

Tavola di verità di \(\vee\)

Implicazione

L’implicazione \(\mathrm{P} \to \mathrm{Q}\) è falsa quando \(\mathrm{P}\) è vera e \(\mathrm{Q}\) è falsa, vera in tutti gli altri casi.

Tavola di verità di \(\to\)

Bi-implicazione

Infine, \(\mathrm{P} \leftrightarrow \mathrm{Q}\) è vera se e solo se \(\mathrm{P}\) e \(\mathrm{Q}\) sono entrambe vere oppure entrambe false.

Tavola di verità di \(\leftrightarrow\)

Calcolo delle tavole di verità

Tavole di verità

Fissiamo una famiglia di proposizioni elementari, che non possono essere ulteriormente analizzate mediante i connettivi logici; tali proposizioni verranno indicate con le lettere \(\mathrm{A}\), \(\mathrm{B}\), \(\mathrm{C}\), ….

Utilizzando le tavole di verità dei connettivi, possiamo calcolare la tavola di verità di ciascuna espressione costruita a partire da tali lettere applicando (ripetutamente) vari connettivi.

Esempio 1

Per esempio la tavola di verità della proposizione \[\underbrace{( \mathrm{B} \to \mathrm{A} ) \wedge ( ( \mathrm{B} \vee \mathrm{C} ) \leftrightarrow \mathrm{A} )}_{\mathrm{P}}\] è la seguente:

Come è stata costruita questa tavola?

Si considerano innanzitutto tutte le possibili situazioni, ovvero tutte le possibili combinazioni di vero/falso per le lettere \(\mathrm{A}\), \(\mathrm{B}\) e \(\mathrm{C}\) a partire dalle quali la proposizione analizzata è stata costruita. Ciascuna “combinazione” corrisponderà ad una riga della tavola di verità.

Nel nostro caso ci sono \(2^3 = 8\) righe. Più in generale, poiché per ogni lettera ci sono due possibilità (vero o falso), se la proposizione contiene \(n\) lettere diverse allora ci saranno \(2^n\) righe.

Poi si calcolano i valori di verità delle proposizioni che compongono \(\mathrm{P}\), cominciando da quelle più semplici e continuando con quelle via via più complicate... fino a calcolare i valori di verità di \(\mathrm{P}\).

Ciascuna colonna viene calcolata utilizzando la tavola di verità del connettivo corrispondente. Quando si è calcolata la colonna dei valori di verità di \(\mathrm{P}\), la tavola è terminata.

Come si “legge” una tavola di verità?

In qualunque contesto ci troviamo, si dovrà ricadere in una delle possibilità considerate (ovvero saremo nella situazione descritta da una delle righe della tavola di verità): il valore di verità di \(\mathrm{P}\) nella riga corrispondente ci dirà allora se l’affermazione \(\mathrm{P}\) sarà vera o falsa in tale contesto.

Ad esempio, se ci troviamo in un contesto in cui \(\mathrm{A}\) è vera, \(\mathrm{B}\) è falsa e \(\mathrm{C}\) è vera, allora ci troveremo nella situazione corrispondente alla terza riga della tavola di verità: controllando il valore di verità di \(\mathrm{P}\) su tale riga, avremo allora che \(\mathrm{P}\) è vera in tale contesto. Se invece siamo in un contesto in cui \(\mathrm{A}\) e \(\mathrm{B}\) sono false mentre \(\mathrm{C}\) è vera,allora la riga corrispondente sarà la settima: concludiamo che in tale contesto \(\mathrm{P}\) è falsa.

Esempio 2

Tavola di verità di \(\mathrm{A} \wedge (\mathrm{B} \to \neg \mathrm{A}).\)

Esempio 3

Esercizi

Calcolare le tavole di verità delle proposizioni seguenti:

• \(\neg (\mathrm{A} \leftrightarrow \mathrm{C}) \vee \mathrm{A}\)

• \(\mathrm{C} \to (\neg \mathrm{A} \vee \neg \mathrm{C})\)

• \((\mathrm{A} \vee \neg (\mathrm{B} \to \mathrm{C})) \wedge (\neg \mathrm{C} \vee \mathrm{B})\)

• \(\mathrm{A} \wedge \neg (\mathrm{A} \to \neg (\neg \mathrm{A} \vee \mathrm{A}))\)

• \((\mathrm{A} \wedge \mathrm{B}) \wedge (\mathrm{A} \vee \mathrm{B}) \wedge (\mathrm{A} \to \mathrm{B})\)

Conseguenza logica

Le tavole di verità ci permettono di dare un significato rigoroso al concetto di conseguenza logica, nonchè un metodo operativo per capire quando una proposizione è conseguenza logica di altre.

Siano \(\mathrm{Q},\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\) proposizioni costruite utilizzando i connettivi a partire da lettere \(\mathrm{A}\), \(\mathrm{B}\), \(\mathrm{C}\), …. Ricordiamo che \[\mathrm{P}_{1} , \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\] (“\(\mathrm{Q}\) è conseguenza logica di \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\)”) se in ogni contesto in cui valgono \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) vale anche \(\mathrm{Q}\).

Poiché ogni contesto determina un’assegnazione di opportuni valori di verità alle lettere \(\mathrm{A}\), \(\mathrm{B}\), \(\mathrm{C}\), …possiamo dire che

\(\mathrm{Q}\) è conseguenza logica di \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\), in simboli \[\mathrm{P}_{1} , \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\] se ogni assegnazione di valori di verità alle lettere contenute in qualcuna tra \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} ,\mathrm{Q}\) che rende vere tutte le proposizioni \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\) rende vera anche la proposizione \(\mathrm{Q}\).

Per dire che \(\mathrm{Q}\) non è conseguenza logica delle proposizioni \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\) scriveremo \[\mathrm{P}_{1} , \dotsc, \mathrm{P}_{n} \not\models \mathrm{Q}\]

Questa riformulazione del concetto di conseguenza logica ci permette di avere un metodo algoritmico per determinare se una data proposizione \(\mathrm{Q}\) è conseguenza logica di certe proposizioni \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) oppure no.

1. Si costruisce la tavola di verità delle proposizioni coinvolte, ovvero \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\), \(\mathrm{Q}\). Più precisamente, si individuano tutte le lettere proposizionali che compaiono in qualcuna di tali proposizioni e si calcolano in un’unica tavola di verità (con \(2^k\) righe, se sono state individuate \(k\) lettere) i valori di verità di ciascuna delle proposizioni \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\), \(\mathrm{Q}\).

2. Si controllano le righe nelle quali ciascuna delle \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) risulta vera. Se in ciascuna di tali righe anche \(\mathrm{Q}\) risulta vera, allora concludiamo che \[\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q} .\] Se su almeno una di tali righe \(\mathrm{Q}\) risulta falsa, allora concludiamo che \[\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \not\models \mathrm{Q} .\]

Date \(\underbrace{\mathrm{A} \to \mathrm{B}}_{\mathrm{P}_{1}} , \underbrace{\mathrm{B} \rightarrow \mathrm{C}}_{\mathrm{P}_{2}}\) e \(\underbrace{\neg \mathrm{A} \vee \mathrm{C}}_{\mathrm{Q}}\),

determiniamo se \[\mathrm{P}_{1} , \mathrm{P}_{2}\models \mathrm{Q} .\]

Costruiamo la tabella di verità (con \(2^3=8\) righe) delle tre proposizioni partendo dalle lettere \(\mathrm{A}\), \(\mathrm{B}\) e \(\mathrm{C}\).

Identifichiamo innanzitutto quali sono le righe in cui sia \(\mathrm{P}_{1}\) che \(\mathrm{P}_{2}\) sono vere: in questo caso sono le righe \(1,5,7,8\).

In ciascuna di queste righe, controlliamo se \(\mathrm{Q}\) è vera: poiché questo accade, concludiamo che \[\mathrm{P}_{1}, \mathrm{P}_{2} \models \mathrm{Q}.\]

Attenzione! Nell’esempio precedente, per calcolare la tavola di verità di \(\mathrm{P}_{1}\) basterebbe considerare solo le lettere \(\mathrm{A}\) e \(\mathrm{B}\). Similmente, per calcolare la tavola di verità di \(\mathrm{P}_{2}\) basterebbe considerare solo le lettere \(\mathrm{B}\) e \(\mathrm{C}\).

Tuttavia, per determinare se \(\mathrm{P}_{1}, \mathrm{P}_{2} \models \mathrm{Q}\) non basta calcolare separatamente le tre tavole di verità di \(\mathrm{P}_{1}\), \(\mathrm{P}_{2}\) e \(\mathrm{Q}\). Bisogna invece calcolare un’unica tavola di verità utilizzando le lettere \(\mathrm{A}\), \(\mathrm{B}\) e \(\mathrm{C}\), ovvero tutte le lettere che compaiono in almeno una delle proposizioni coinvolte.

Verifichiamo che

\[\underbrace{(\mathrm{A} \vee \mathrm{B}) \rightarrow \mathrm{C}}_{\mathrm{P}} \models \underbrace{\mathrm{A} \rightarrow \mathrm{C}}_{\mathrm{Q}}\]

Le righe in cui \(\mathrm{P}\) è vera sono le righe \(1,3,5,7,8\) : poiché in tali righe anche \(\mathrm{Q}\) è vera, concludiamo che \[\mathrm{P}\models\mathrm{Q}.\]

Verifichiamo ora che

\[\underbrace{(\mathrm{A} \wedge \mathrm{B}) \rightarrow \mathrm{C}}_{\mathrm{P}} \not\models \underbrace{\mathrm{A} \rightarrow \mathrm{C}}_{\mathrm{Q}}.\]

Le righe in cui \(\mathrm{P}\) è vera sono le righe \(1,3,4,5,6,7,8\). Nelle righe \(1,3,5,6,7,8\) anche \(\mathrm{Q}\) è vera. Tuttavia, nella riga \(4\), che è una di quelle in cui \(\mathrm{P}\) era vera, \(\mathrm{Q}\) è falsa:

questo basta per concludere che \[\mathrm{P}\not\models \mathrm{Q} .\]

Indicare per ciascuna delle seguenti righe se vale la relazione di conseguenza logica indicata, motivando la risposta con la corrispondente tavola di verità:

1. \(\neg \mathrm{A} \vee \neg \mathrm{B} \models \neg \mathrm{A} \to \neg \mathrm{B}\)

2. \(\mathrm{A} \to \mathrm{B} \models \mathrm{A} \vee \mathrm{B}\)

3. \(\neg \mathrm{B} \to \neg \mathrm{A} \models \neg \mathrm{A} \vee \mathrm{B}\)

4. \(\neg \mathrm{A} \wedge \neg \mathrm{B} \models \neg \mathrm{A} \to \neg \mathrm{B}\)

5. \(\mathrm{A} \vee \mathrm{B} \models \mathrm{A}\)

6. \(\mathrm{A} \vee \mathrm{B} \models \mathrm{B}\)

(Soluzione alla lavagna)

Quanto visto finora ci permette di controllare la validità di alcune delle leggi logiche che abbiamo visto nella Sezione 1.2. Consideriamo la

Legge della disgiunzione \(\mathrm{P} \vee \mathrm{Q}, \neg \mathrm{P} \models \mathrm{Q}\).

Qualunque sia il contesto in cui valutiamo \(\mathrm{P}\) e \(\mathrm{Q}\), ricadremo in una delle possibilità descritte dalla quattro righe seguenti. Utilizzando le tavole di verità dei connettivi calcoliamo

L’unica situazione in cui entrambe le formule a sinistra del simbolo di conseguenza logica sono vere è quella corrispondente alla terza riga; su tale riga, la formula a destra del simbolo di conseguenza logica è vera, quindi abbiamo verificato che effettivamente \[\mathrm{P} \vee \mathrm{Q}, \neg \mathrm{P} \models \mathrm{Q}.\]

\[\mathrm{P}, \mathrm{P} \to \mathrm{Q} \models \mathrm{Q}.\]

Verificare utilizzando le tavole di verità la validità delle seguenti leggi logiche:

• \(\mathrm{P} \models \mathrm{Q} \vee \neg \mathrm{Q}\)

• \(\mathrm{P} \wedge \neg \mathrm{P} \models \mathrm{Q}\)

• \(\mathrm{P}, \mathrm{Q} \models \mathrm{P} \wedge \mathrm{Q}\)

• \(\mathrm{P} \wedge \mathrm{Q} \models \mathrm{P}\)

• \(\mathrm{P} \wedge \mathrm{Q} \models \mathrm{Q}\)

• \(\mathrm{P} \models \mathrm{P} \vee \mathrm{Q}\)

• \(\mathrm{Q} \models \mathrm{P} \vee \mathrm{Q}\)

Equivalenza logica

Ricordiamo che \(\mathrm{P}\) e \(\mathrm{Q}\) sono (logicamente) equivalenti se in ogni contesto in cui è vera una è vera anche l’altra, e viceversa. Poiché lavorare in un dato contesto significa essenzialmente assegnare dei valori di verità a \(\mathrm{P}\) e \(\mathrm{Q}\), possiamo riformulare questa nozione come segue:

Due proposizioni \(\mathrm{P}\) e \(\mathrm{Q}\) si dicono logicamente equivalenti, in simboli \[\mathrm{P} \equiv \mathrm{Q},\] se ogni assegnazione di valori di verità alle lettere contenute in \(\mathrm{P}\) e \(\mathrm{Q}\) dà lo stesso valore di verità a entrambe le proposizioni, ovvero se le (colonne finali delle) tavola di verità di \(\mathrm{P}\) e \(\mathrm{Q}\) coincidono su ogni riga.

Per dire che \(\mathrm{P}\) e \(\mathrm{Q}\) non sono logicamente equivalenti scriveremo \[\mathrm{P} \not\equiv \mathrm{Q}\]

Questa riformulazione del concetto di equivalenza logica ci permette nuovamente di avere un metodo algoritmico per determinare se una data proposizione \(\mathrm{P}\) è logicamente equivalente ad un’altra proposizione \(\mathrm{Q}\) oppure no.

1. Si costruisce la tavola di verità delle due proposizioni \(\mathrm{P}\) e \(\mathrm{Q}\). Più precisamente, si individuano tutte le lettere proposizionali che compaiono in una delle due proposizioni e si calcolano in un’unica tavola di verità (con \(2^k\) righe, se sono state individuate \(k\) lettere) i valori di verità di entrambe le proposizioni \(\mathrm{P}\) e \(\mathrm{Q}\).

2. Si controllano tutte le righe della tavola di verità così ottenuta. Se in ciascuna riga \(\mathrm{P}\) e \(\mathrm{Q}\) hanno lo stesso valore di verità (ovvero sono entrambe vere oppure entrambe false), allora concludiamo che \[\mathrm{P} \equiv \mathrm{Q} .\] Se su almeno una di tali righe \(\mathrm{P}\) e \(\mathrm{Q}\) hanno valori di verità diversi (ovvero una è vera mentre l’altra è falsa), allora concludiamo che \[\mathrm{P} \not\equiv \mathrm{Q} .\]

Ad esempio, per verificare che \[\underbrace{(\mathrm{A} \to \mathrm{B} ) \wedge \neg \mathrm{B}}_{\mathrm{P}} \equiv \underbrace{\neg (\mathrm{A} \vee \mathrm{B})}_{\mathrm{Q}}\]

calcoliamo le tavole di verità di \(\mathrm{P}\) e \(\mathrm{Q}\) in un’unica tabella:

Controlliamo ora riga per riga che \(\mathrm{P}\) e \(\mathrm{Q}\) abbiano gli stessi valori di verità in ogni possibile situazione. Poiché questo accade, possiamo concludere che effettivamente \[\mathrm{P} \equiv \mathrm{Q}.\]

Controllando la tavola di verità dell’esercizio precedente, possiamo osservare che \[(\mathrm{A} \to \mathrm{B}) \wedge \neg \mathrm{B} \models \neg (\mathrm{A} \vee \mathrm{B})\] e \[\neg (\mathrm{A} \vee \mathrm{B}) \models (\mathrm{A} \to \mathrm{B}) \wedge \neg \mathrm{B}.\]

Questo accade perché, come discusso nella Sezione 1.1, in generale si ha

\(\mathrm{P} \equiv \mathrm{Q}\)

se e solo se

\(\mathrm{P} \models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{P}\).

Dimostrare che \[\underbrace{\mathrm{A} \leftrightarrow \mathrm{B}}_{\mathrm{P}} \not \equiv \underbrace{(\mathrm{A} \rightarrow \mathrm{B}) \vee (\mathrm{B} \rightarrow \mathrm{A})}_{\mathrm{Q}}\]

Possiamo osservare che nell’esempio precedente \[\mathrm{A} \leftrightarrow \mathrm{B} \models (\mathrm{A} \rightarrow \mathrm{B}) \vee (\mathrm{B} \rightarrow \mathrm{A})\] (infatti nella colonna finale della tavola di verità di \((\mathrm{A} \rightarrow \mathrm{B}) \vee (\mathrm{B} \rightarrow \mathrm{A})\) compaiono solo V), mentre \[(\mathrm{A} \rightarrow \mathrm{B}) \vee (\mathrm{B} \rightarrow \mathrm{A}) \not\models \mathrm{A} \leftrightarrow \mathrm{B}.\]

Indicare per ciascuna delle seguenti righe se vale la relazione di equivalenza logica indicata, motivando la risposta con la corrispondente tavola di verità:

1. \(\neg \mathrm{A} \wedge \neg \mathrm{B} \equiv \neg \mathrm{A} \to \neg \mathrm{B}\)

2. \(\mathrm{A} \to \mathrm{B} \equiv \neg \mathrm{A} \vee \mathrm{B}\)

3. \(\neg \mathrm{B} \to \neg \mathrm{A} \equiv \neg \mathrm{A} \vee \mathrm{B}\)

4. \(\neg (\mathrm{A} \to \mathrm{B}) \equiv \mathrm{A} \wedge \neg \mathrm{B}\)

5. \(\mathrm{A} \to \mathrm{B} \equiv \mathrm{B} \to \mathrm{A}\)

6. \((\mathrm{A} \to \mathrm{B}) \to \mathrm{C} \equiv \mathrm{A} \to (\mathrm{B} \to \mathrm{C})\)

(Soluzione alla lavagna)

Quanto visto a riguardo dell’equivalenza logica ci permette di controllare la validità di molte altre leggi logiche e proprietà viste nella Sezione 1.2. Cominciamo con la

Proprietà distributiva di \(\vee\) su \(\wedge\) \[\mathrm{P} \vee ( \mathrm{Q} \wedge \mathrm{R} ) \equiv ( \mathrm{P} \vee \mathrm{Q} ) \wedge ( \mathrm{P} \vee \mathrm{R} ) .\]

Qualunque sia il contesto in cui ci troviamo, si dovrà ricadere in una delle situazioni descritte dalle \(8\) righe seguenti. Calcoliamo...

Poiché su ogni riga (ovvero in ogni situazione) le due proposizioni hanno gli stessi valori di verità, possiamo concludere che sono logicamente equivalenti.

Esercizio 4

Utilizzando le tavole di verità, dimostrare la validità della proprietà distributiva di \(\wedge\) su \(\vee\): \[\mathrm{P} \wedge ( \mathrm{Q} \vee \mathrm{R} ) \equiv ( \mathrm{P} \wedge \mathrm{Q} ) \vee ( \mathrm{P} \wedge \mathrm{R} ) .\]

Verifichiamo ora che vale la

Proprietà associativa di \(\leftrightarrow\) \((\mathrm{P} \leftrightarrow \mathrm{Q}) \leftrightarrow \mathrm{R} \equiv \mathrm{P} \leftrightarrow (\mathrm{Q} \leftrightarrow \mathrm{R})\).

Esercizio 5

Utilizzando le tavole di verità, dimostrare la validità delle due leggi di De Morgan:

\(\neg (\mathrm{P} \wedge \mathrm{Q}) \equiv \neg \mathrm{P} \vee \neg \mathrm{Q}\) e \(\neg (\mathrm{P} \vee \mathrm{Q}) \equiv \neg \mathrm{P} \wedge \neg \mathrm{Q}\).

Esercizio 6

Utilizzando le tavole di verità, dimostrare la validità delle seguenti leggi logiche:

• \(\mathrm{P} \equiv \neg \neg \mathrm{P}\)

• \(\mathrm{P} \wedge \mathrm{Q} \equiv \neg (\neg \mathrm{P} \vee \neg \mathrm{Q})\)

• \(\mathrm{P} \vee \mathrm{Q} \equiv \neg (\neg \mathrm{P} \wedge \neg \mathrm{Q})\)

• \(\mathrm{P} \to \mathrm{Q} \equiv \neg \mathrm{P} \vee \mathrm{Q}\)

• \(\mathrm{P} \to \mathrm{Q} \equiv \neg (\mathrm{P} \wedge \neg \mathrm{Q})\)

• \(\mathrm{P} \leftrightarrow \mathrm{Q} \equiv (\mathrm{P} \to \mathrm{Q}) \wedge (\mathrm{Q} \to \mathrm{P} )\)

Tautologie

Una proposizione si dice valida o tautologia se è vera per ogni assegnazione di valori di verità alle lettere che contiene, ovvero se nella (colonna finale della) sua tavola di verità compaiono solo V.

Per dire che \(\mathrm{P}\) è una tautologia scriveremo anche \[\models \mathrm{P}\]

La proposizione \(\mathrm{A} \vee \neg \mathrm{A}\) è una tautologia. Infatti

Esempi Legge di Peirce \(((\mathrm{A} \rightarrow \mathrm{B}) \rightarrow \mathrm{A}) \rightarrow \mathrm{A}\)

Legge di Dummet \(( \mathrm{A} \to \mathrm{B} ) \vee (\mathrm{B} \to \mathrm{A})\)

Osserviamo che \(\mathrm{Q}\) è conseguenza logica di \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\), in simboli \[\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\] se e solo se la proposizione \((\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}) \rightarrow \mathrm{Q}\) è una tautologia, in simboli \[\models (\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}) \rightarrow \mathrm{Q}.\]

Questo ci dà anche un modo alternativo per controllare se \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\) utilizzando le tavole di verità: si calcola la tavola di verità di \((\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}) \rightarrow \mathrm{Q}\) e si controlla che in ogni riga tale proposizione risulti vera.

Dimostrare che \[\underbrace{\mathrm{A} \vee \mathrm{B}}_{\mathrm{P}_{1}}, \underbrace{\mathrm{C}}_{\mathrm{P}_{2}} \models \underbrace{(\mathrm{A} \vee \mathrm{B}) \leftrightarrow \mathrm{C}}_{\mathrm{Q}}.\]

Similmente, ricordiamo che \(\mathrm{P}\) e \(\mathrm{Q}\) sono logicamente equivalenti, in simboli \[\mathrm{P} \equiv \mathrm{Q}\] se e solo se la proposizione \(\mathrm{P} \leftrightarrow \mathrm{Q}\) è una tautologia, in simboli \[\models \mathrm{P} \leftrightarrow \mathrm{Q}.\]

Questo ci dà anche un modo alternativo per controllare se \(\mathrm{P} \equiv \mathrm{Q}\) utilizzando le tavole di verità: si calcola la tavola di verità di \(\mathrm{P} \leftrightarrow \mathrm{Q}\) e si controlla che in ogni riga tale proposizione risulti vera.

Esempio

Dimostrare che \[\underbrace{\mathrm{A} \wedge \mathrm{B}}_{\mathrm{P}} \equiv \underbrace{\neg(\mathrm{A} \to \neg \mathrm{B})}_{\mathrm{Q}}.\]

Contraddizioni

Una proposizione \(\mathrm{P}\) è insoddisfacibile o una contraddizione se è falsa per ogni assegnazione di valori di verità alle lettere che contiene, ovvero tale che nella (colonna finale della) sua tavola di verità compaiono solo F.

Si osservi che \(\mathrm{P}\) è una tautologia se e solo se \(\neg \mathrm{P}\) è una contraddizione.

La proposizione \(\mathrm{A} \wedge \neg \mathrm{A}\) è una contraddizione. Infatti

Esempio

La formula \[(\neg \mathrm{A} \leftrightarrow \mathrm{B}) \wedge (\mathrm{A} \rightarrow \mathrm{B}) \wedge (\mathrm{B} \rightarrow \mathrm{A})\] è una contraddizione.

Soddisfacibilità

Una proposizione \(\mathrm{P}\) è soddisfacibile se è vera per qualche assegnazione di valori di verità alle lettere che contiene, ovvero è tale che nella (colonna finale della) sua tavola di verità compare almeno una V.

Si osservi che \(\mathrm{P}\) è soddisfacibile se e solo se \(\mathrm{P}\) non è una contraddizione. Inoltre, ogni tautologia è ovviamente soddisfacibile, ma vi sono proposizioni soddisfacibili che non sono tautologie.

Esempio

La formula \[(\mathrm{A} \vee \neg \mathrm{A} ) \rightarrow (\mathrm{A} \rightarrow \mathrm{B})\] è soddisfacibile ma non è una tautologia.

(Soluzione alla lavagna)

Dimostrare che la proposizione \[(\mathrm{A} \vee \mathrm{B} \vee \mathrm{C}) \wedge (\mathrm{A} \rightarrow (\neg \mathrm{B} \wedge \mathrm{C})) \wedge \neg \mathrm{B} \wedge (\mathrm{C} \rightarrow (\mathrm{A} \wedge \neg \mathrm{A}))\] è una contraddizione.

(Soluzione alla lavagna)

Dimostrare che la proposizione \[((\mathrm{A} \wedge \mathrm{B}) \rightarrow \mathrm{C}) \wedge (\mathrm{C} \rightarrow \neg \mathrm{A})\] è soddisfacibile.

(Soluzione alla lavagna)

La formula \((\neg \mathrm{A} \vee \mathrm{B}) \rightarrow (\mathrm{A} \wedge \mathrm{B})\) è soddisfacibile? È una tautologia o una contraddizione?

(Soluzione alla lavagna)

Tecniche di dimostrazione

Le tavole di verità ci permettono inoltre di giustificare in maniera rigorosa la correttezza delle tecniche dimostrative viste nella Sezione 1.1, ovvero

• Dimostrazione per assurdo,

• Dimostrazione per contrapposizione,

• Dimostrazione per composizione (o interpolazione),

• Dimostrazione per casi.

Dimostrazione per assurdo

Cominciamo con la dimostrazione per assurdo. Per dimostrare che \[\mathrm{P} \models \mathrm{Q}\] si dimostra che assumere \(\mathrm{P}\) e \(\neg \mathrm{Q}\) porta ad una contraddizione, in simboli \[\mathrm{P}, \neg \mathrm{Q} \models \mathrm{R} \wedge \neg \mathrm{R}\] per qualche \(\mathrm{R}\).

Osseviamo che per verificare la correttezza di questo ragionamento, basta mostrare che

\((\mathrm{P} \wedge \neg \mathrm{Q}) \to (\mathrm{R} \wedge \neg \mathrm{R}) \models \mathrm{P} \to \mathrm{Q}.\)

Infatti, una volta stabilito (una volta per tutte!) che vale la conseguenza logica

\((\mathrm{P} \wedge \neg \mathrm{Q}) \to (\mathrm{R} \wedge \neg \mathrm{R}) \models \mathrm{P} \to \mathrm{Q}\)

ci troveremo nella situazione seguente:

se per certe specifiche \(\mathrm{P}\), \(\mathrm{Q}\) ed \(\mathrm{R}\) riusciamo a dimostrare che \(\mathrm{P}, \neg \mathrm{Q} \models (\mathrm{R} \wedge \neg \mathrm{R})\), allora vuol dire che \((\mathrm{P} \wedge \neg \mathrm{Q}) \to (\mathrm{R} \wedge \neg \mathrm{R})\) è una tautologia. Per la conseguenza logica precedente, ne consegue che anche \(\mathrm{P} \to \mathrm{Q}\) è una tautologia: questo è equivalente ad asserire \(\mathrm{P} \models \mathrm{Q}\), che è proprio il teorema che dovevamo dimostrare.

Quindi ogni volta che dimostriamo qualcosa del tipo \[\mathrm{P} , \neg \mathrm{Q} \models (\mathrm{R} \wedge \neg \mathrm{R})\] sappiamo che anche \[\mathrm{P} \models \mathrm{Q}\] è vero: questo è proprio lo schema di dimostrazione per assurdo!

Verifichiamo quindi che

\((\mathrm{P} \wedge \neg \mathrm{Q}) \to (\mathrm{R} \wedge \neg \mathrm{R}) \models \mathrm{P} \to \mathrm{Q} .\)

Qualunque sia il contesto in cui ci troviamo, ricadremo in una delle \(8\) possibilità seguenti:

Osservazione. In questo caso si ha addirittura che le due formule sono logicamente equivalenti, quindi dimostrare \(\mathrm{P}, \neg \mathrm{Q} \models \mathrm{R} \wedge \neg \mathrm{R}\) è in realtà equivalente a dimostrare \(\mathrm{P} \models \mathrm{Q}\).

Dimostrazione per contrapposizione

Abbiamo poi visto la dimostrazione per contrapposizione. Per dimostrare che \[\mathrm{P} \models \mathrm{Q}\] dimostriamo che \[\neg \mathrm{Q} \models \neg \mathrm{P}.\]

Ragionando come nel caso della dimostrazione per assurdo, si vede che per stabilire la correttezza di questo schema dimostrativo basta verificare (Esercizio!) che \[\neg \mathrm{Q} \to \neg \mathrm{P} \models \mathrm{P} \to \mathrm{Q}.\]

Osservazione. Anche in questo caso risulta che \(\neg \mathrm{Q} \to \neg \mathrm{P} \equiv \mathrm{P} \to \mathrm{Q}\), ovvero che dimostrare \(\neg \mathrm{Q} \models \neg \mathrm{P}\) è in realtà equivalente a dimostrare \(\mathrm{P} \models \mathrm{Q}\).

Dimostrazione per composizione (o interpolazione)

Lievemente diverso è il caso della dimostrazione per composizione (o interpolazione). Per dimostrare \[\mathrm{P} \models \mathrm{Q}\] dimostriamo che

\(\mathrm{P} \models \mathrm{R}\) e \(\mathrm{R} \models \mathrm{Q}\)

per un opportuno \(\mathrm{R}\).

Per giustificare lo schema è sufficiente verificare (slide seguente) che \[(\mathrm{P} \to \mathrm{R}) \wedge (\mathrm{R} \to \mathrm{Q}) \models \mathrm{P} \to \mathrm{Q}.\]

A differenza dei casi precedenti, vedremo però che \((\mathrm{P} \to \mathrm{R}) \wedge (\mathrm{R} \to \mathrm{Q})\) e \(\mathrm{P} \to \mathrm{Q}\) non sono logicamente equivalenti: quindi quando si usa questa strategia si dimostra qualcosa di potenzialmente più forte del teorema \(\mathrm{P} \models \mathrm{Q}\) da dimostrare.

\((\mathrm{P} \to \mathrm{R}) \wedge (\mathrm{R} \to \mathrm{Q}) \models \mathrm{P} \to \mathrm{Q}\).

Qualunque sia il contesto in cui lavoriamo, ricadremo in una delle \(8\) possibilità seguenti:

La stessa tavola di verità mostra che invece \[\mathrm{P} \to \mathrm{Q} \not\models (\mathrm{P} \to \mathrm{R}) \wedge (\mathrm{R} \to \mathrm{Q})\] e quindi che le due formule non sono logicamente equivalenti.

Dimostrazione per casi Infine, consideriamo la dimostrazione per casi. Per semplificare la trattazione considereremo solo il caso in cui si distinguano due casi \(\mathrm{P}_{1}\) e \(\mathrm{P}_{2}\), lasciando al lettore la verifica del caso generale.

Dimostrazione per casi

Per dimostrare che \[\mathrm{P}_{1} \vee \mathrm{P}_{2} \models \mathrm{Q}\] dimostriamo che

\(\mathrm{P}_{1} \to \mathrm{Q}\) e \(\mathrm{P}_{2} \to \mathrm{Q}\).

Per verificare la correttezza di questo ragionamento basta verificare che \[(\mathrm{P}_{1} \to \mathrm{Q}) \wedge (\mathrm{P}_{2} \to \mathrm{Q}) \models (\mathrm{P}_{1} \vee \mathrm{P}_{2}) \to \mathrm{Q}.\]

Lasciamo al lettore il compito di verificare questo fatto utilizzando le tavole di verità

(in realtà le due formule risultano logicamente equivalenti)

.

Osserviamo inotre che

\((\mathrm{P} \vee \neg \mathrm{P}) \to \mathrm{Q} \equiv \mathrm{Q}\)

Infatti

Utilizzando anche quanto visto nella slide precedente, otteniamo

\((\mathrm{P} \to \mathrm{Q}) \wedge (\neg \mathrm{P} \to \mathrm{Q})\) \(\equiv\) \((\mathrm{P} \vee \neg \mathrm{P}) \to \mathrm{Q}\) \(\equiv\) \(\mathrm{Q}\).

Possiamo quindi concludere che per dimostrare \[\models \mathrm{Q}\] possiamo dimostrare

\(\mathrm{P} \models \mathrm{Q}\) e \(\neg \mathrm{P} \models \mathrm{Q}\)

per una qualunque proposizione \(\mathrm{P}\).

Rompicapo

La logica proposizionale permette di risolvere in maniera semplice e sicura diversi rompicapo a prima vista molto complicati.

• Né Alberto né Carlo sono buoni studenti.

• (Alberto è un buon studente se Davide lo è ), oppure, ( se ( Davide o Elisabetta sono buoni studenti) allora (Carlo è un buon studente se e solo se Davide lo è)).

Nella situazione descritta dalle proposizioni qui sopra, Davide è un buon studente?

• Né Alberto né Carlo sono buoni studenti.

• (Alberto è un buon studente se Davide lo è), oppure, (se (Davide o Elisabetta sono buoni studenti) allora (Carlo è un buon studente se e solo se Davide lo è)).

Nella situazione descritta dalle proposizioni qui sopra, Davide è un buon studente?

Cominciamo con l’introdurre una lettera per ognuna delle proposizioni elementari considerate:

• \(\mathrm{A} \leadsto\) Alberto è un buon studente

• \(\mathrm{C} \leadsto\) Carlo è un buon studente

• \(\mathrm{D} \leadsto\) Davide è un buon studente

• \(\mathrm{E} \leadsto\) Elisabetta è una buona studentessa

Traduciamo poi le due condizioni in formule della logica proposizionale, utilizzando i connettivi nella maniera opportuna:

• \(\neg \mathrm{A} \wedge \neg \mathrm{C}\)

• \(( \mathrm{D} \to \mathrm{A} ) \vee \left ((\mathrm{D} \vee \mathrm{E} ) \to ( \mathrm{C} \leftrightarrow \mathrm{D} ) \right )\)

• Né Alberto né Carlo sono buoni studenti.

• (Alberto è un buon studente se Davide lo è), oppure, (se (Davide o Elisabetta sono buoni studenti) allora (Carlo è un buon studente se e solo se Davide lo è)).

Nella situazione descritta dalle proposizioni qui sopra, Davide è un buon studente?

La richiesta fatta consiste dunque nel determinare se \[\neg \mathrm{A} \wedge \neg \mathrm{C} , ( \mathrm{D} \to \mathrm{A} ) \vee \left ((\mathrm{D} \vee \mathrm{E} ) \to ( \mathrm{C} \leftrightarrow \mathrm{D} ) \right ) \models \mathrm{D}\] oppure \[\neg \mathrm{A} \wedge \neg \mathrm{C}, ( \mathrm{D} \to \mathrm{A} ) \vee \left ((\mathrm{D} \vee \mathrm{E} ) \to ( \mathrm{C} \leftrightarrow \mathrm{D} ) \right ) \models \neg \mathrm{D}.\]

Attenzione! Potrebbe anche darsi che nessuna delle due relazioni di conseguenza logica precedenti valga: in questo caso dovremmo concludere che i dati non consentono di risolvere il problema posto.

Calcoliamo l’opportuna tavola di verità. Per brevità, sia \(\mathrm{Q}\) la proposizione \((\mathrm{D} \vee \mathrm{E} ) \to ( \mathrm{C} \leftrightarrow \mathrm{D} )\).

• Se Alberto ordina un caffè altrettanto fa Beatrice.

• Al più uno tra Beatrice e Carlo ordina un caffè.

• Alberto o Carlo, o entrambi, ordinano un caffè.

• Se Carlo ordina un caffè, altrettanto fa Alberto.

Chi ordina un caffè?

Introduciamo opportune lettere per le proposizioni elementari:

• \(\mathrm{A} \leadsto\) Alberto ordina un caffé

• \(\mathrm{B} \leadsto\) Beatrice ordina un caffé

• \(\mathrm{C} \leadsto\) Carlo ordina un caffé

Le condizioni precedenti diventano:

• \(\mathrm{A} \to \mathrm{B}\)

• \(\neg (\mathrm{B} \wedge \mathrm{C})\)

• \(\mathrm{A} \vee \mathrm{C}\)

• \(\mathrm{C} \to \mathrm{A}\).

Calcoliamo la tavola di verità delle proposizioni precedenti: